//给你一个 互不相同 的整数数组，其中 locations[i] 表示第 i 个城市的位置。同时给你 start，finish 和 fuel 分别表示出发城市
//、目的地城市和你初始拥有的汽油总量 
//
// 每一步中，如果你在城市 i ，你可以选择任意一个城市 j ，满足 j != i 且 0 <= j < locations.length ，并移动到城市 
//j 。从城市 i 移动到 j 消耗的汽油量为 |locations[i] - locations[j]|，|x| 表示 x 的绝对值。 
//
// 请注意， fuel 任何时刻都 不能 为负，且你 可以 经过任意城市超过一次（包括 start 和 finish ）。 
//
// 请你返回从 start 到 finish 所有可能路径的数目。 
//
// 由于答案可能很大， 请将它对 10^9 + 7 取余后返回。 
//
// 
//
// 示例 1： 
//
// 
//输入：locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
//输出：4
//解释：以下为所有可能路径，每一条都用了 5 单位的汽油：
//1 -> 3
//1 -> 2 -> 3
//1 -> 4 -> 3
//1 -> 4 -> 2 -> 3
// 
//
// 示例 2： 
//
// 
//输入：locations = [4,3,1], start = 1, finish = 0, fuel = 6
//输出：5
//解释：以下为所有可能的路径：
//1 -> 0，使用汽油量为 fuel = 1
//1 -> 2 -> 0，使用汽油量为 fuel = 5
//1 -> 2 -> 1 -> 0，使用汽油量为 fuel = 5
//1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 3
//1 -> 0 -> 1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 5
// 
//
// 示例 3： 
//
// 
//输入：locations = [5,2,1], start = 0, finish = 2, fuel = 3
//输出：0
//解释：没有办法只用 3 单位的汽油从 0 到达 2 。因为最短路径需要 4 单位的汽油。 
//
// 
//
// 提示： 
//
// 
// 2 <= locations.length <= 100 
// 1 <= locations[i] <= 10⁹ 
// 所有 locations 中的整数 互不相同 。 
// 0 <= start, finish < locations.length 
// 1 <= fuel <= 200 
// 
//
// Related Topics 记忆化搜索 数组 动态规划 👍 114 👎 0

package leetcode.editor.cn;

import java.util.Arrays;

//java:统计所有可行路径
public class Q1575CountAllPossibleRoutes {
    public static void main(String[] args){
        Solution solution = new Q1575CountAllPossibleRoutes().new Solution();
        solution.countRoutes(new int[]{2,3,6,8,4}, 1, 3, 5);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    int mod = 1000000007;
//    int[][] cached;
//    public int countRoutes(int[] locations, int start, int finish, int fuel) {
//        int n = locations.length;
//        // 从start出发，使用fuel燃料能够到达的路径数量
//        cached = new int[n][fuel + 1];
//        // 默认到达的数量为全部为-1，与0做区分
//        for (int i = 0; i < n; i++) {
//            Arrays.fill(cached[i], -1);
//        }
//        return dfs(locations, start, finish, fuel);
//    }
//
//    /**
//     * 计算到达的路径数量
//     * @param locations 路径图
//     * @param start 开始的坐标
//     * @param finish 结束的坐标
//     * @param fuel 使用的燃料
//     * @return
//     */
//    public int dfs(int[] locations, int start, int finish, int fuel) {
//        // 已经记录有路径数直接返回
//        if (cached[start][fuel] != -1) return cached[start][fuel];
//        // 返回条件一：燃料没有，并且到达的路径不是结束的路径是，记录0
//        if (fuel == 0 && start != finish) {
//            cached[start][fuel] = 0;
//            return 0;
//        }
//
//        // 返回条件二：燃料还有，但是已经无法到达任何路径，到达任何路径所需要的燃料都大于fuel
//        boolean hasNext = false;
//        for (int i = 0; i < locations.length; i++) {
//            int dis = Math.abs(locations[start] - locations[i]);
//            if (start != i && fuel >= dis) {
//                    hasNext = true;
//                    break;
//            }
//        }
//        if (fuel != 0 && !hasNext) {
//            cached[start][fuel] = (start == finish) ? 1 : 0;
//            return cached[start][fuel];
//        }
//
//        // 计算路径总数
//        int sum = (start == finish) ? 1 : 0;
//        for (int i = 0; i < locations.length; i++) {
//            int dis = Math.abs(locations[start] - locations[i]);
//            if (start != i && fuel >= dis) {
//                // 遍历+回溯，计算从i开始到结束的总数
//                sum += dfs(locations, i, finish, fuel - dis);
//                sum = sum % mod;
//            }
//        }
//        cached[start][fuel] = sum;
//        return sum;
//    }
        // 解法二
    public int countRoutes(int[] locations, int start, int finish, int fuel) {
        int n = locations.length;
        // f[i][j] 代表从位置 i 出发，当前油量为 j 时，到达目的地的路径数
        int[][] dp = new int[n][fuel + 1];

        // 对于本身位置就在目的地的状态，路径数为 1
        for (int i = 0; i < fuel + 1; i++) dp[finish][i] = 1;

        // 从状态转移方程可以发现 f[i][fuel]=f[i][fuel]+f[k][fuel-need]
        // 在计算 f[i][fuel] 的时候依赖于 f[k][fuel-need]
        // 其中 i 和 k 并无严格的大小关系
        for (int curFuel = 0; curFuel < fuel + 1; curFuel++) {
            for (int i = 0; i < n; i++) {
                for (int k = 0; k < n; k++) {
                    if (i != k) {
                        int needFuel = Math.abs(locations[i] - locations[k]);
                        // 而 fuel 和 fuel-need 具有严格大小关系：fuel >= fuel-need
                        // 因此需要先从小到大枚举油量
                        if (curFuel >= needFuel) {
                            dp[i][curFuel] = dp[i][curFuel] + dp[k][curFuel - needFuel];
                            dp[i][curFuel] %= mod;
                        }
                    }
                }
            }
        }
        return dp[start][fuel];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}